const int SZ = 300010;
const int ALP = 26 + 10;

struct PAM {
	char s[SZ]; int tree[SZ][ALP], fail[SZ], len[SZ], cnt[SZ];
	int tot, last;
	
	PAM() {s[0] = -1; fail[0] = 1; len[1] = -1; tot = 1;}
	
	void init(char str[]) {
		strcpy(s + 1, str + 1); return;
	}
	
	int newnode(int x) {
		len[++tot] = x; return tot;
	}
	
	int getfail(int x, int n) {
		while (s[n - len[x] - 1] != s[n]) x = fail[x];
		return x;
	}
	
	void build() {
		for (int i = 1; s[i]; i++) {
			s[i] -= 'a';
			int p = getfail(last, i);
			if (!tree[p][s[i]]) {
				int q = newnode(len[p] + 2);
				fail[q] = tree[getfail(fail[p], i)][s[i]];
				tree[p][s[i]] = q;
			}
			++cnt[last = tree[p][s[i]]];
		}
	}
} pam;